package day;

import beans.Trie;
import javafx.util.Pair;

import java.util.*;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;

/**
 * 212. 单词搜索 II
 */
public class P212 {
    public List<String> findWords(char[][] board, String[] words) {
        int row = board.length;
        int col = board[0].length;
        //1. 将单词按首字母放到Map中
        Map<Character, List<Pair>> beginMap = new HashMap<>();
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                List<Pair> pairs = beginMap.getOrDefault(board[r][c], new ArrayList<>());
                pairs.add(new Pair(r, c));
                beginMap.put(board[r][c], pairs);
            }
        }
        //2. 遍历匹配单词
        List<String> resultList = new ArrayList<>();
        ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
        List<ForkJoinTask<Boolean>> futureTasks = new ArrayList<>();
        for (String word : words) {
            ForkJoinTask<Boolean> task = forkJoinPool.submit(() -> {
                if (word.length() > 0 && beginMap.containsKey(word.charAt(0))) {
                    for (Pair<Integer, Integer> pair : beginMap.get(word.charAt(0))) {
                        int[][] mask = new int[row][col];
                        mask[pair.getKey()][pair.getValue()] = 1;
                        if (match(word.toCharArray(), board, mask, 0, pair.getKey(), pair.getValue())) {
                            resultList.add(word);
                            break;
                        }
                        mask[pair.getKey()][pair.getValue()] = 0;
                    }
                }
                return false;
            });
            futureTasks.add(task);
        }
        for (ForkJoinTask<Boolean> task : futureTasks) {
            task.join();
        }
        return resultList;
    }

    //
    private boolean match(char[] word, char[][] board, int[][] mask, int pos, int r, int c) {
        if (pos == word.length - 1) {
            return true;
        } else {
            int[][] directions = new int[][]{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
            //寻找下一个有效位置
            for (int[] direct : directions) {
                int nr = r + direct[0];
                int nc = c + direct[1];
                if (0 <= nr && nr < board.length && 0 <= nc && nc < board[0].length && mask[nr][nc] == 0 && board[nr][nc] == word[pos + 1]) {
                    mask[nr][nc] = 1;
                    if (match(word, board, mask, pos + 1, nr, nc)) {
                        return true;
                    }
                    mask[nr][nc] = 0;
                }
            }
            return false;
        }
    }


    /**
     * 使用前缀树
     */
    public List<String> trieFindWords(char[][] board, String[] words) {
        //1. 创建前缀树
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        //2.
        Set<String> resultSet = new HashSet<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, trie, new StringBuilder(), resultSet);
            }
        }
        return new ArrayList<>(resultSet);
    }

    private void dfs(char[][] board, int r, int c, Trie trie, StringBuilder sb, Set<String> resultSet) {
        char ch = board[r][c];
        int idx = ch - 'a';
        if (board[r][c] == '#' || trie.childs[idx] == null) {
            return;
        } else {//未结束
            if (trie.childs[idx].isEnd) {
                sb.append(ch);
                resultSet.add(sb.toString());
                sb.deleteCharAt(sb.length() - 1);
            }


            int[][] directs = new int[][]{
                    {0, -1}, {0, 1}, {-1, 0}, {1, 0}
            };
            sb.append(ch);
            board[r][c] = '#';
            for (int[] direct : directs) {
                int nr = r + direct[0];
                int nc = c + direct[1];
                if (0 <= nr && nr < board.length && 0 <= nc && nc < board[0].length) {
                    dfs(board, nr, nc, trie.childs[idx], sb, resultSet);
                }
            }
            board[r][c] = ch;
            sb.deleteCharAt(sb.length() - 1);
        }

    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}
        };
        String[] words = new String[]{"oath", "pea", "eat", "rain"};
        List<String> words1 = new P212().trieFindWords(board, words);
        System.out.println(words1);
    }
}

